刷题笔记：探索乘积小于K的子数组问题

篇首语：本文由编程笔记#小编为大家整理，主要介绍了刷题日记乘积小于K的子数组相关的知识，希望对你有一定的参考价值。

给定一个正整数数组 nums 和整数 k &＃xff0c;请找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums &＃61; [10,5,2,6], k &＃61; 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。


示例 2:

输入: nums &＃61; [1,2,3], k &＃61; 0
输出: 0


提示:

• 1 <&＃61; nums.length <&＃61; 3 * 10^4
• 1 <&＃61; nums[i] <&＃61; 1000
• 0 <&＃61; k <&＃61; 10^6

题目链接

思路一&＃xff1a;前缀和 &＃43; 二分

二分查找常用函数&＃xff1a;

头文件 #include

• upper_bound(begin, end, num) &＃xff1a;返回在 [begin, end) 二分查找的**第一个大于 num** 的数的索引&＃xff0c;不存在返回 end
• lower_bound(begin, end, num) &＃xff1a;返回在 [begin, end) 二分查找的**第一个大于等于 num** 的数的索引&＃xff0c;不存在返回 end

算法思路&＃xff1a;

• 使用乘积作为二分的依据&＃xff0c;会出现 整形溢出&＃xff0c;防止溢出&＃xff0c;等式两边取对数&＃xff1a;

  
  

  • mul[i&＃43;1] &＃61; mul[i] * nums[i]; //乘积会整型溢出
// 等式两边取对数
log(mul[i&＃43;1]) &＃61; log(mul[i] * nums[i]) &＃61; log(mul[i]) &＃43; log(nums[i]);
// 乘积变为对数和
// 令 sum[i] &＃61; log(mul[i])
sum[i&＃43;1] &＃61; sum[i] &＃43; log(nums[i]);


• 题目所求为 乘积小于k的子数组&＃xff0c;遍历每个数字 nums[i]&＃xff0c;枚举区间左端点 i &＃xff0c;找最小边界 bound&＃xff0c;满足&＃xff1a;

  
  
  • i <&＃61; bound
  • nums[i]*num[i&＃43;1]*...*nums[bound] >&＃61; k 即 sum[bound] - sum[i-1] >&＃61; log(k)
  • 找 第一个bound&＃xff0c;sum[bound] >&＃61; log(k) &＃43; sum[i-1] &＃61;&＃61;> 使用 lower_bound

• 注意&＃xff1a;因为涉及到对数&＃xff0c;因此 sum[] 数组使用 double 类型

  
  

  
  

  double 类型只保证15位小数精确&＃xff0c;为防止计算误差&＃xff1a;

  
  

  1. 题目中 1 <&＃61; nums[i] <&＃61; 1000 且 1 <&＃61; nums.length <&＃61; 3 * 10^4&＃xff0c;可得最大乘积为1000^3*10^4&＃xff0c;取对数为 30000*ln(1000)&＃xff0c;ln(1000)&＃61;6.9 &＃xff0c;整数数位最大为6位

  2. 防止计算误差&＃xff08;即15位后省去的小数&＃xff09;&＃xff0c;小数最少为9位&＃xff0c;加上 1e-10

     sum[bound] - sum[i-1] &＃43; 1e-10 >&＃61; log(k)

  
  

  条件&＃xff1a;sum[bound] >&＃61; log(k) &＃43; sum[i -1] - 1e-10

• 对每个区间左端点 i &＃xff0c;找到的边界 bound&＃xff0c;则以下区间均满足条件&＃xff1a;

  
  

  
  

  [i, i], [i, i&＃43;1], [i, i&＃43;2],..., [i, bound-1]

  
  

  共 bound - 1 - i &＃43; 1 &＃61; bound - i 个区间

代码&＃xff1a;

class Solution
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k)
int n &＃61; nums.size();
// long long mul[n&＃43;1];
double sum[n&＃43;1];
for(int i &＃61; 0;i < n;i &＃43;&＃43; )
// mul[i&＃43;1] &＃61; mul[i] * nums[i]; //乘积会整型溢出
// 等式两边取对数 log(mul[i&＃43;1]) &＃61; log(mul[i] * nums[i]) &＃61; log(mul[i]) &＃43; log(nums[i])
// 令 sum[i] &＃61; log(mul[i])
sum[i&＃43;1] &＃61; sum[i] &＃43; log(nums[i]);

int cnt &＃61; 0;
for(int i &＃61; 1;i <&＃61; n;i &＃43;&＃43; )
int l &＃61; lower_bound(sum &＃43; i, sum &＃43; n &＃43; 1, sum[i-1] &＃43; log(k) - 1e-10) - sum;
cnt &＃43;&＃61; (l - i);

return cnt;

;
// 遍历每个i 二分找第一个乘积大于等于k的边界bound 则i...bound-1都满足条件


时间复杂度&＃xff1a;O(nlogn)

空间复杂度&＃xff1a;O(n)

思路二&＃xff1a;滑动窗口

双指针 left, right

算法思路&＃xff1a;

• 窗口右边界逐个递增&＃xff08;迭代&＃xff09;
• 当[left, right] 内乘积 prod >&＃61; k 时&＃xff0c;窗口左边界右移&＃xff0c;减小窗口&＃xff0c;直到 prod 为止
• 过程中不断叠加统计 [left, right] 内的新增的子区间数量